#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <unordered_set>
#include <stack>

using namespace std;

// 207. 课程表
class Solution1
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        vector<vector<int>> g(numCourses);
        vector<int> inDeg(numCourses);
        for(auto& e : prerequisites)
        {
            int x = e[0], y = e[1];
            g[y].push_back(x);
            ++inDeg[x];
        }

        queue<int> q;
        for(int i = 0; i < numCourses; ++i)
        {
            if(inDeg[i] == 0) q.push(i);
        }

        int visited = 0;
        while(!q.empty())
        {
            ++visited;
            int x = q.front();
            q.pop();
            for(int y : g[x])
            {
                if(--inDeg[y] == 0) q.push(y);
            }
        }

        return visited == numCourses;
    }
};

// LCR 113. 课程表 II
class Solution2
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        vector<vector<int>> g(numCourses);
        vector<int> inDeg(numCourses);
        for(auto& e : prerequisites)
        {
            int x = e[0], y = e[1];
            g[y].push_back(x);
            ++inDeg[x];
        }

        queue<int> q;
        for(int i = 0; i < numCourses; ++i) if(!inDeg[i]) q.push(i);

        vector<int> ret;
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            ret.push_back(x);
            for(int y : g[x])
            {
                if(--inDeg[y] == 0) q.push(y);
            }
        }

        if(ret.size() != numCourses) return {};
        return ret;
    }
};

// 630. 课程表 III
class Solution3
{
public:
    int scheduleCourse(vector<vector<int>>& courses) 
    {
        sort(courses.begin(), courses.end(), [&](const auto& a, const auto& b){
            return a[1] < b[1]; // 按照 lastDay 从小到大排序
        });

        priority_queue<int> pq; // 保存 duration 的最大值
        int day = 0; // 已消耗的时间
        for(auto& c : courses)
        {
            int duration = c[0], lastDay = c[1];
            if(day + duration <= lastDay)
            {
                day += duration;
                pq.push(duration);
            }
            else if(!pq.empty() && duration < pq.top()) // 该课程的时间比之前的最长时间要短
            {
                // 反悔，撤销之前 duration 最长的课程，改成学习该课程
                day -= pq.top() - duration;
                pq.pop();
                pq.push(duration);
            }
        }

        return pq.size();
    }
};

// 1462. 课程表 IV
class Solution4
{
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) 
    {
        vector<vector<int>> g(numCourses);
        vector<int> inDeg(numCourses);
        for(auto& e : prerequisites)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            ++inDeg[y];
        }

        queue<int> q;
        for(int i = 0; i < numCourses; ++i) if(!inDeg[i]) q.push(i);

        vector<vector<bool>> isPre(numCourses, vector<bool>(numCourses));
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            for(int y : g[x])
            {
                isPre[x][y] = true;
                for(int i = 0; i < numCourses; ++i)
                {
                    isPre[i][y] = isPre[i][y] | isPre[i][x]; 
                }

                if(--inDeg[y] == 0) q.push(y);
            }
        }

        vector<bool> ret;
        for(auto& q : queries)
        {
            int x = q[0], y = q[1];
            ret.push_back(isPre[x][y]);
        }
        return ret;
    }
};

// 871. 最低加油次数
class Solution5
{
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) 
    {
        priority_queue<int> pq;
        int ret = 0, prev = 0, fuel = startFuel;
        int n = stations.size();
        for(int i = 0; i <= n; ++i)
        {
            int cur = i < n ? stations[i][0] : target;
            fuel -= cur - prev;
            while(fuel < 0 && !pq.empty())
            {
                fuel += pq.top();
                pq.pop();
                ++ret;
            }
            if(fuel < 0) return -1;

            if(i < n)
            {
                pq.emplace(stations[i][1]);
                prev = cur;
            }
        }

        return ret;
    }
};

// LCP 30. 魔塔游戏
class Solution6
{
public:
    int magicTower(vector<int>& nums) 
    {
        long blood = 1;
        for(int x : nums) blood += x;
        if(blood <= 0) return -1;

        blood = 1;
        int ret = 0, n = nums.size();
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] < 0)
            {
                pq.push(nums[i]);
                if(blood + nums[i] <= 0)
                {
                    ++ret;
                    blood += -pq.top();
                    pq.pop();
                }
            }
            blood += nums[i];
        }

        return ret;
    }
};

// 2813. 子序列最大优雅度
class Solution7
{
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) 
    {
        // 把利润从大到小排序
        sort(items.begin(), items.end(), [](const auto& a, const auto& b){
            return a[0] > b[0];
        });

        long long ret = 0, totalProfit = 0;
        unordered_set<int> visited;
        stack<int> duplicate; // 重复类别的利润
        for(int i = 0; i < items.size(); ++i)
        {
            int profit = items[i][0], category = items[i][1];
            if(i < k)
            {
                totalProfit += profit;
                if(!visited.insert(category).second) // 重复类别
                    duplicate.push(profit);
            }
            else if(!duplicate.empty() && visited.insert(category).second)
            {
                totalProfit += profit - duplicate.top();
                duplicate.pop();
            }
            ret = max(ret, totalProfit + (long long)visited.size() * (long long)visited.size());
        }

        return ret;
    }
};

